/*
题目: 解数独
编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

    数字 1-9 在每一行只能出现一次。
    数字 1-9 在每一列只能出现一次。
    数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

https://leetcode.cn/problems/sudoku-solver
 */
public class SolveSudoku {
    private boolean[][] row = new boolean[9][9];  // 判断某一行, 中所有元素的访问情况
    private boolean[][] col = new boolean[9][9];  // 判断某一列, 中所有元素的访问情况
    private boolean[][][] cell = new boolean[3][3][9]; // 九宫格, 某一行 + 某一列 对应 9 个数字的出现情况
    private List<int[]> spaces = new ArrayList<> (); // 记录空格位置, 主要就是将空格填满
    private boolean completed = false; // 完成

    public void solveSudoku(char[][] board) {
        // 预处理
        for (int i = 0; i < 9; i ++) {
            for (int j = 0; j < 9; j ++) {
                if (board[i][j] != '.') {
                    int digit = board[i][j] - '1';
                    row[i][digit] = col[j][digit] = cell[i / 3][j / 3][digit] = true;
                } else {
                    spaces.add(new int[] {i, j});
                }
            }
        }

        backTrack(board, 0);
    }

    private void backTrack(char[][] board, int pos) {
        if (pos >= spaces.size()) {
            completed = true;
            return ;
        }

        int[] cur = spaces.get(pos);
        // 在这个空格上 尝试添加字符 且满足题意
        for (char ch = '1'; ch <= '9'; ch ++) {
            int digit = ch - '1';
            if (!completed && !row[cur[0]][digit] && !col[cur[1]][digit] && !cell[cur[0] / 3][cur[1] / 3][digit]) {
                board[cur[0]][cur[1]] = ch;
                row[cur[0]][digit] = col[cur[1]][digit] = cell[cur[0] / 3][cur[1] / 3][digit] = true;
                backTrack(board, pos + 1);

                row[cur[0]][digit] = col[cur[1]][digit] = cell[cur[0] / 3][cur[1] / 3][digit] = false;
            }
        }
    }
}
